package main

import (
	"fmt"
)

/**
执行用时：4 ms, 在所有 Go 提交中击败了53.39%的用户
内存消耗：3.8 MB, 在所有 Go 提交中击败了49.94%的用户
 */
var dx = []int{-1, 0, 1, 0}
var dy = []int{0, 1, 0, -1}
var g [][]byte

func numIslands(grid [][]byte) int {

	g = grid
	cnt := 0
	n, m := len(grid), len(grid[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == '1' {
				cnt++
				dfs(i, j)
			}
		}
	}
	return cnt
}

func dfs(x int, y int) {
	g[x][y] = '0'
	for i := 0; i < 4; i++ {
		a, b := x + dx[i], y + dy[i]
		if a >= 0 && a < len(g) && b >= 0 && b < len(g[0]) && g[a][b] == '1' {
			dfs(a, b)
		}
	}
}

func main() {

	grid := [][]byte {
		{'1', '1', '0', '0', '0'},
		{'1', '1', '0', '0', '0'},
		{'0', '0', '1', '0', '0'},
		{'0', '0', '0', '1', '1'},
	}
	fmt.Println(numIslands(grid))  // 3
}
